import java.io.*;
import java.nio.Buffer;
import java.util.HashMap;
import java.util.zip.GZIPOutputStream;

/**
 * @author 03010570
 * @date 2020/07/06
 * describe:    LeetCode ： 63、 不同路径2 https://leetcode-cn.com/problems/unique-paths-ii/
 */
public class LeetCode_64 {

    public static void main(String[] args) throws IOException {
        int[][] ints = new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(minPathSum(ints));
    }

    /**
     * 二维数组 DP
     * 把 第一行 和 第一列单独处理
     * 时间复杂度 ： O(M*N)   M 二维数组行的长度， N 二维数组列的长度
     * 空间复杂度 ： O(M*N)   M 二维数组行的长度， N 二维数组列的长度
     *
     * @param grid
     * @return
     */
    public static int minPathSum2(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length;
        int columns = grid[0].length;
        int[][] dp = new int[rows][columns];
        dp[0][0] = grid[0][0];
        // 第一行 单独处理当前单元格的值
        for (int i = 1; i < rows; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }
        // 第一列 单独处理当前单元格的值
        for (int j = 1; j < columns; j++) {
            dp[0][j] = grid[0][j] + dp[0][j - 1];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                // 将 上一行当前列 和 当前行上一列比较取 较小值
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][columns - 1];
    }

    /**
     * 一维数组 DP
     * 把 第一行单独处理
     * 第一列单独处理 在循环内部单独处理
     * 时间复杂度 ： O(M*N)   M 二维数组行的长度， N 二维数组列的长度
     * 空间复杂度 ： O(N)     N 二维数组列的长度
     * @param grid
     * @return
     */
    public static int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length;
        int columns = grid[0].length;
        // 一维数组取列的数量
        int[] dp = new int[columns];
        dp[0] = grid[0][0];
        // 单独处理 第一行数据
        for (int i = 1; i < columns; i++) {
            dp[i] = dp[i - 1] + grid[0][i];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (j == 0) {
                    // 滚动数组：每次循环取值时 对 第一列单独处理，上一列的值 + 当前单元格的值
                    dp[j] = dp[j] + grid[i][j];
                } else {
                    //  当前行的上一个列 和 上一列的当前行 取较小值
                    dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
                }
            }
        }
        return dp[columns - 1];
    }
}
